#include "test5.h"

/* 二叉树  */
void test5(void)
{
    TreeRoot *T = CreateTree();
    TreeStoreyPrint(T);
}


TreeRoot *CreateTree(void)
{
    TreeRoot *root = (TreeRoot *)malloc(sizeof(TreeRoot));
    TreeNode *A = (TreeNode *)malloc(sizeof(TreeNode));
    TreeNode *B = (TreeNode *)malloc(sizeof(TreeNode));
    TreeNode *C = (TreeNode *)malloc(sizeof(TreeNode));
    TreeNode *D = (TreeNode *)malloc(sizeof(TreeNode));
    TreeNode *E = (TreeNode *)malloc(sizeof(TreeNode));
    TreeNode *F = (TreeNode *)malloc(sizeof(TreeNode));
    TreeNode *G = (TreeNode *)malloc(sizeof(TreeNode));
    TreeNode *H = (TreeNode *)malloc(sizeof(TreeNode));
    TreeNode *K = (TreeNode *)malloc(sizeof(TreeNode));

    A->data = 'A';
    B->data = 'B';
    C->data = 'C';
    D->data = 'D';
    E->data = 'E';
    F->data = 'F';
    G->data = 'G';
    H->data = 'H';
    K->data = 'K';

    A->lefttree  = B;
    A->righttree = E;
    B->lefttree  = NULL;
    B->righttree = C;
    E->lefttree  = NULL;
    E->righttree = F;
    C->lefttree  = D;
    C->righttree = NULL;
    F->lefttree  = G;
    F->righttree = NULL;
    D->lefttree  = NULL;
    D->righttree = NULL;
    G->lefttree  = H;
    G->righttree = K;
    H->lefttree  = NULL;
    H->righttree = NULL;
    K->lefttree  = NULL;
    K->righttree = NULL;
    root->treeroot = A;
    return root;

}

// 二叉树按层遍历
int TreeStoreyPrint(TreeRoot *root)
{
    int i=0;
    TreeRoot *T = root;
    TreeNode *tem = (TreeNode *)malloc(sizeof(TreeNode));
    linkq_t *P  = CreatListSeq();
    InsertListSeq(P, T->treeroot);

    PrintAllLinkq(P);
    while ( P->front->next != NULL )
    {
        /* code */
        tem = GetOutListSeq(P);
        printf("    %c\n", tem->data);
        if( tem->lefttree != NULL ){
            InsertListSeq(P, tem->lefttree);
        }
        if( tem->righttree != NULL ){
            InsertListSeq(P, tem->righttree);
        }
        // PrintAllLinkq(P);
    }
    return 0;
}

/*********************************************** 链式队列 *************************************************/
linkq_t *CreatListSeq(void)
{
    linkq_t *p;
    q_t *s;
    s = (q_t *)malloc(sizeof(q_t));
    s->tree = NULL;
    s->next = NULL;
    p = (linkq_t *)malloc(sizeof(linkq_t));
    p->front = s;
    p->rear  = s;
    p->len   = 0;
    return p;
}

int InsertListSeq(linkq_t *linkq, TreeNode *root)
{
    q_t *p = (q_t *)malloc(sizeof(q_t));
    p->tree = root;
    p->next = NULL;
    linkq->rear->next = p;
    linkq->rear = p;
    linkq->len++;
    return 0;
}

TreeNode *GetOutListSeq(linkq_t *linkq)
{
    TreeNode *root;
    if( linkq->len == 0 ){
        printf("err empty\n");
        return NULL;
    }
    else if( linkq->len == 1 ){
        root = linkq->front->next->tree;
        linkq->front->next = NULL;
        linkq->rear = linkq->front;
        linkq->len--;
        return root;
    }
    root = linkq->front->next->tree;
    linkq->front->next = linkq->front->next->next;
    linkq->len--;
    return root;
}

// 遍历打印
int PrintAllLinkq(linkq_t *linkq)
{
    if( linkq->len == 0 ){
        printf("err empty\n");
        return 1;
    }
    q_t *p;
    p = linkq->front->next;
    for(int i=1; i<linkq->len+1; i++){
        printf("p[%d]=%c  ",i,p->tree->data);
        p = p->next;
    }
    printf("\n");
}
/*********************************************** ******** *************************************************/
